package Stack;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

public class _503_NextGreaterElementII {
    //hint:the element can be duplicate and the array is circle.
    public int[] nextGreaterElements(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        int[] numss = new int[nums.length * 2];
        for (int i = 0; i < numss.length; i++) {
            numss[i] = nums[i % nums.length];
        }
        Stack<Integer> stack = new Stack();
        for (int j = 0; j <numss.length; j++) {
            while (!stack.isEmpty() && numss[stack.peek()] < numss[j]) {
                map.put(stack.pop(), numss[j]);
            }
            stack.push(j);
        }

        for (int i = 0; i < nums.length; i++) {
            nums[i] = map.getOrDefault(i, -1);
        }
        return nums;
    }
}
